The present invention relates to managing exclusive control of a shareable resource between a plurality of concurrently executing threads, and more particularly, publishing a claim to a lock for a thread that is next to own the lock.
Concurrent algorithms (except those in the lock free class) utilize some sort of access control mechanism to ensure synchronization, that is, individual access to shared resources. Using mutual exclusion locks, for example, each thread, before accessing an individual shared resource, must acquire a lock in order to continue, or, if the lock is not available, the thread must wait until it has been released by the current owner of the lock.
In this context, thread waiting can be achieved in two possible ways. A busy lock may be used, in which the thread enters a tight loop inspecting the lock, continuing until the lock is found to be free. A passive lock may be used, in which the thread queues itself in a linked list of waiting threads and suspends execution, waiting to be woken up by the lock owner once the lock is available.
Prior art busy locks generally fall into two main classes of locking algorithms: unfair and fair. Generally, in unfair locking algorithms each lock requester loops fighting against all other lock requester until the lock requester detects that it has obtained the lock. Acquisition of the lock occurs more by chance than by design because acquisition of the lock is dependent on the relative timings of execution of instructions by all the competing lock requester threads. Conversely, in fair locking algorithms, access to the shareable resource protected by the lock is ordered and each lock requester waits for the previous lock requester in the order to have completed whatever critical section work the lock controls before the thread starts using the lock itself. The lock itself may maintain an ordered lists of threads requesting ownership of the lock.
Busy locks suffer from many side effects, which are common across both unfair and fair classes. Generally, fair and unfair locks are complementary in the way in which each is successful, or unsuccessful, in dealing with the side effects. The most striking difference is that in unfair lock algorithms, the lock owner is known to have acquired the lock, while in fair locks the lock owner is presumed to have done so.